一.概念
1.回文自动机
回文自动机,又叫回文树,是一种能在时间玄学解决回文串问题的一种结构,代码难度也十分和蔼可亲。
回文树上的每个节点都代表一个不同的回文子串,相同的回文子串在同一节点。
值得注意的是,回文树上有两个根,0根以及-1根,分别表示空串和-1串,其本质是考虑奇串和偶串。
回文树上有两种边,一种是转移边,另一种是后缀边。
2.转移边
若回文串 有一条 的转移边到 ,说明存在一个回文串 两端各增加1个字符 ,将形成回文串 。
特殊的,对于 根的转移边,表示单个字符表示的回文串,如 。
3.后缀边
若回文串 有一条后缀边连接到 ,说明 是 的最大回文串后缀(不含 自身)。
对于 根和 根,其后缀边都连向 根,为的是统一奇串和偶串。
因为每个节点只会向上有一条后缀边,所以所有后缀边会形成一棵树。
4.例子
黑色的边为转移边,红色的边为后缀边。

如图,5号节点代表的回文串为 , 9号节点代表的回文串为
二.构造
和后缀自动机一样,回文自动机使用增量法构造。在构造之前,定义一些变量:
, 点 前后各增加一个字符 得到的点。
, 点 的后缀边指向的点。
, 点 所表示的回文串的长度。特殊的,为了得到奇串 根的 为 。
表示需要构造的串的第 位。
, 为右端点的最长回文子串的标号(必定存在,因为可以单独一个字符作为回文串)。
若 ,即 的最长回文串无法通过前后拓展一个字符 形成更长的回文串。
那么我们将 设为 ,寻找它的最长回文后缀,最终一定能找到。最坏情况下来到 根 , 此时一定满足条件。将现在到达的点记为 。
找到后,说明 可以前后加上 形成一个更长的回文串,那么为右端点的最长回文串就找到了。
-
若此时 不等于 ,也就是已经有一个这样的回文串了,那么将 设置为 , 结束。
-
若不存在这样的回文串,需要新建一个节点 表示这个回文串。将 设为 ,并将 设为 。顺着 的 链走,直到再次出现 的位置, 此时将 连向 即可。
图解过程可以看看这篇博客。
三.复杂度
1.空间复杂度
空间复杂度是 ,是字符串长度 , 是字符集大小。
不过可以通过优化空间。
2.时间复杂度
并不会证明,大概是建立后缀边的时候,一旦走过了一个点,之后再在后缀链上走时将会跳过该点。也就是复杂度均摊 。
五.例题
先附一份模板:
struct Palindromes_Automaton {
int Size , Last , Root0 , Root1 , Trans[ MAXN + 5 ][ MAXK + 5 ] , Link[ MAXN + 5 ];
int Len[ MAXN + 5 ];
Palindromes_Automaton( ) {
Root0 = Size ++ , Root1 = Size ++; Last = Root1;
Len[ Root0 ] = 0 , Link[ Root0 ] = Root1;
Len[ Root1 ] = -1 , Link[ Root1 ] = Root1;
}
void Extend( int ch , int dex ) {
int u = Last;
for( ; str[ dex ] != str[ dex - Len[ u ] - 1 ] ; u = Link[ u ] );
if( !Trans[ u ][ ch ] ) {
int Newnode = ++ Size , v = Link[ u ];
Len[ Newnode ] = Len[ u ] + 2;
for( ; str[ dex ] != str[ dex - Len[ v ] - 1 ] ; v = Link[ v ] );
Link[ Newnode ] = Trans[ v ][ ch ]; Trans[ u ][ ch ] = Newnode;
}
Last = Trans[ u ][ ch ];
}
void Build( char *str ) {
int len = strlen( str );
for( int i = 0 ; i < len ; i ++ )
Extend( str[ i ] - 'a' + 1 , i );
}
}PAM;
int main() {
scanf("%s", str );
PAM.Build( str );
printf("%lld", PAM.Calc( ) );
return 0;
}